package leetcode.code0646;

import java.util.Arrays;

import leetcode.IDebug;

public class Solution implements IDebug {
	
	public int findLongestChain(int[][] pairs) {
		// [[1,2], [2,3], [3,4]]
		Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
		int[] len = new int[1000];
		Arrays.fill(len, Integer.MAX_VALUE);
		int ans = 0;
		for (int i = 0; i < pairs.length; i++) {
			int[] pair = pairs[i];
			int c = pair[0], v = pair[1];
			int j = 0;
			// 遍历找j ， pairs[i]能达到的最大长度-1
			while (j < len.length && c > len[j]) {
				j++;
			}
			if (v < len[j]) {
				len[j] = v;
				ans = Math.max(ans, j);
			}
		}
		return ans + 1;
	}
	

	public int findLongestChain3(int[][] pairs) {
		Arrays.sort(pairs, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
		int[] len = new int[1000];
		Arrays.fill(len, Integer.MAX_VALUE);
		int ans = 0;
		for (int i = 0; i < pairs.length; i++) {
			int[] pair = pairs[i];
			int c = pair[0], v = pair[1];
			if (i > 0 && c == pairs[i - 1][0]) {
				continue;
			}
			int l = 0, r = ans + 1;
			int j = 0;
			while (l <= r) {
				int m = ((r - l) >> 1) + l;
				if (len[m] >= c) {
					j = m;
					r = m - 1;
				} else {
					l = m + 1;
				}
			}
			if (v < len[j]) {
				len[j] = v;
			}
			ans = Math.max(ans, j);
		}
		return ans + 1;
	}

	public int findLongestChain1(int[][] pairs) {
		// [[1,2], [2,3], [3,4]]
		Arrays.sort(pairs, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
		int[] len = new int[1000];
		Arrays.fill(len, Integer.MAX_VALUE);
		int ans = 0;
		for (int i = 0; i < pairs.length; i++) {
			int[] pair = pairs[i];
			int c = pair[0], v = pair[1];
			int l = 0, r = 1000;
			int j = 0;
			while (l <= r) {
				int m = ((r - l) >> 1) + l;
				if (len[m] >= c) {
					j = m;
					r = m - 1;
				} else {
					l = m + 1;
				}
			}
//			while (j < len.length && c > len[j]) {
//				j++;
//			}
			if (v < len[j]) {
				len[j] = v;
			}
			ans = Math.max(ans, j);
		}
		return ans + 1;
	}

	class Solution2 {
		public int findLongestChain(int[][] pairs) {
			// [[1,2], [2,3], [3,4]]
			Arrays.sort(pairs, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
			int[] len = new int[1000];
			Arrays.fill(len, Integer.MAX_VALUE);
			int ans = 0;
			for (int i = 0; i < pairs.length; i++) {
				int[] pair = pairs[i];
				int c = pair[0], v = pair[1];
				int j = 0;
				while (j < len.length && c > len[j]) {
					j++;
				}
				if (v < len[j]) {
					len[j] = v;
				}
				ans = Math.max(ans, j);
			}
			return ans + 1;
		}
	}

//	作者：wa-pian-d
//	链接：https://leetcode.cn/problems/maximum-length-of-pair-chain/solution/646-zui-chang-shu-dui-lian-by-wa-pian-d-9ftp/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	class Solution1 {
		public int findLongestChain(int[][] pairs) {
			// [[1,2], [2,3], [3,4]]
			Arrays.sort(pairs, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
			int[] len = new int[1000];
			Arrays.fill(len, Integer.MAX_VALUE);
			int ans = 0;
			for (int i = 0; i < pairs.length; i++) {
				int[] pair = pairs[i];
				int c = pair[0], v = pair[1];
				int j = 0;
				while (j < len.length) {
					if (c > len[j]) {
						if (v < len[j]) {// 能更新长度j+1的数链结尾
							len[j] = v;
						}
						j++;// c > len[j] 说明数链能变长。
					} else {
						if (v < len[j]) {// 能更新长度j+1的数链结尾
							len[j] = v;
						}
						ans = Math.max(ans, j);// pairs[i]达到的最远数链，尝试更新答案。
						break;
					}
				}
			}
			return ans + 1;
		}
	}
//
//	作者：wa-pian-d
//	链接：https://leetcode.cn/problems/maximum-length-of-pair-chain/solution/646-zui-chang-shu-dui-lian-by-wa-pian-d-9ftp/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
